package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @author feizns
 * @since 2020/3/10
 */
public class FindDuplicateSubtrees {

    public static void main(String[] args) {

    }

    public static List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        postOrder(root);
        return ret;
    }

    static List<TreeNode> ret = new LinkedList<>();

    static Map<String, Integer> treeNum = new HashMap<>();

    private static String postOrder(TreeNode node) {
        if ( node != null ) {
            String l = postOrder(node.left);
            String r = postOrder(node.right);
            String c = node.val + l + r;
            Integer val = treeNum.get(c);
            val = val != null ? val + 1 : 1;
            if ( val == 2 )
                ret.add(node);
            treeNum.put(c, val);
            return c;
        }
        return "null";
    }

}
